package com.test.daily.leetcode.y2022.m06.day0609.v03;

import java.util.ArrayList;
import java.util.Random;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/6/9 下午 06:46
 * @version: 1.0
 */
public class Solution {

    int[][] rects;
    ArrayList<Integer> list;
    Random random;

    public Solution(int[][] rects){
        this.random = new Random();
        this.rects = rects;
        list = new ArrayList<>();
        list.add(0);
        for(int[] rect: rects){
            int a = rect[0], b = rect[1], x = rect[2], y = rect[3];
            list.add(list.get(list.size() -1) + ((x - a + 1)*(y - b + 1)));
        }
    }
    public int[] pick(){
        int k = this.random.nextInt(this.list.get(this.list.size() - 1));
        int rectIndex = binarySearch(list, k+1) - 1;
        k -= list.get(rectIndex);
        int a = this.rects[rectIndex][0];
        int b = this.rects[rectIndex][1];
        int x = this.rects[rectIndex][2];
        int y = this.rects[rectIndex][3];
        int col = y - b + 1;
        int da = k / col;
        int db = k - col * da;
        return new int[]{a + da, b + db};

    }
    public int binarySearch(ArrayList<Integer> list, int target){
        int low = 0, high = list.size() - 1;
        while(low <= high){
            int mid = low + (high - low) / 2;
            int size = list.get(mid);
            if(size == target){
                return mid;
            } else if(size > target){
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
}
